package org.algorithm.熊猫.数组.三月.第三周;

/**
 * @date 2022-03-15 星期二16:20
 *
 * <p>
 * 给你一个正整数数组arr，请你计算所有可能的奇数长度子数组的和。
 * <p>
 * 子数组 定义为原数组中的一个连续子序列。
 * <p>
 * 请你返回 arr中 所有奇数长度子数组的和 。
 *
 *
 * </p>
 * <p>
 * uri:   https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/
 */
public class 所有偶数长度子数组的和 {


    public static void main(String[] args) {
        System.out.println(2 >> 1);
        System.out.println(3 >> 1);
        System.out.println(4 >> 1);
        int[] arr = {1, 4, 2, 5};
        System.out.println(sumOddLengthSubarrays(arr));
        System.out.println(5+12+6+7);
    }


    /**
     * 输入：arr = [1,4,2,5,3]
     * 输出：58
     * 解释：所有奇数长度子数组和它们的和为：
     * [1] = 1
     * [4] = 4
     * [2] = 2
     * [5] = 5
     * [3] = 3
     * [1,4,2] = 7
     * [4,2,5] = 11
     * [2,5,3] = 10
     * [1,4,2,5,3] = 15
     * 我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
     */
    public static int sumOddLengthSubarrays(int[] arr) {
        int sum = 0;

        for (int i = 0; i < arr.length; i++) {
            int leftCount = i;  //下标为i时，左边元素个数
            int rightCount = arr.length - i - 1; //下标为i时，右边元素个数

            //判断当前数字在整个奇数组出现的次数  偶数-1=奇数
            // 当前数字长度为1， 子数组长度为偶数n,则n-1等于剩余元素个数。 n-1为奇数， 下面列出n-1出现的可能
            // case 1   奇数+偶数=奇数  则获取当前元素左边和右边各自有多少个对应元素
            int leftOdd = (leftCount + 1) >> 1;
            int rightEven = (rightCount >> 1) + 1;
            int ollAll = leftOdd * rightEven;
            // case 2 偶数+奇数=偶数    则获取当前元素左边和右边各自有多少个对应元素
            int leftEven = (leftCount >> 1) + 1;
            int rightOdd = (rightCount + 1) >> 1;
            int evenAll = leftEven * rightOdd;
            sum+=arr[i]*(ollAll+evenAll);
        }
        return sum;
    }
}
